'''
堆排序（Heap Sort）是一种基于比较的排序算法，它利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：
即子节点的键值或索引总是小于（或者大于）它的父节点。
在堆排序算法中，我们首先需要构建一个最大堆（或最小堆），在构建过程中，我们会反复进行下沉（或上浮）操作以保持堆的性质。在最大堆中，
每个父节点的值都大于或等于其子节点的值。构建好最大堆后，堆顶（根节点）的元素就是当前序列中的最大值。接下来，我们将堆顶元素（即最大值）
与堆的最后一个元素交换，然后减小堆的大小（即去掉已排序的最大元素），并对新的堆顶元素执行下沉操作，以保持堆的性质。重复上述过程，
直到堆的大小为1，此时序列即为有序序列。
时间复杂度分析
构建堆：对于一个长度为n的数组，构建最大堆的时间复杂度为O(n)。这是因为每个非叶子节点最多下沉一次，非叶子节点的数量是n/2（对于完全二叉树而言），
所以构建堆的时间复杂度是O(n)。
排序过程：在排序过程中，我们需要进行n-1次堆的调整（因为每次都将堆顶元素与堆的最后一个元素交换，并减少堆的大小），
每次调整的时间复杂度是O(log n)（因为是从堆顶下沉到叶子节点，路径长度为log n）。因此，排序过程的时间复杂度是O(n log n)。
总时间复杂度：构建堆的时间复杂度是O(n)，排序过程的时间复杂度是O(n log n)，所以堆排序的总时间复杂度是O(n log n)。
空间复杂度分析
堆排序不是稳定排序，是一个原地排序算法，它只需要常量级别的额外空间来存储临时变量（如索引或交换时的临时值），不需要额外的存储空间来存放待排序的数组元素。
因此，堆排序的空间复杂度是O(1)。这使得堆排序在需要处理大量数据且内存资源有限的情况下非常有用。
'''
import random
class Solution:
    #构建最小（大）堆
    def heap_build(self,arr,n,i):
        #初始化i为最小节点下标
        small = i
        #当前节点的左右子节点下标
        left = 2*i+1
        right = 2*i+2
        #左节点小
        if left<n and arr[left]<arr[small]:
            small = left
        #右节点更小
        if right<n and arr[right]<arr[small]:
            small = right
        #有交换
        if small!=i:
            arr[small],arr[i] = arr[i],arr[small]
            #对受影响的子节点递归构建最小（大）堆
            self.heap_build(arr,n,small)

    def heap_sort(self, arr):
        n = len(arr)
        #构建最小（大）堆，从n//2-1节点开始
        for i in range(n//2-1,-1,-1):   #注意要构建到根节点0下标
            self.heap_build(arr,n,i)
        #逐次取出堆顶元素
        for i in range(n-1,0,-1):
            arr[i],arr[0] = arr[0],arr[i]
            #对剩余部分继续构造最小（大）堆
            self.heap_build(arr,i,0)
        return arr
#示例
if __name__ == '__main__':
    arr = random.sample(range(100),10)
    print(arr)
    print(Solution().heap_sort(arr))